20. Valid Parentheses

今天要挑戰是第二十題合法括號，這題也是非常經典而且有趣的，其中還會使用「堆疊」(Stack)這樣子的資料結構，能幫助完成題目要求，接下來就讓我們一起來看看這一題吧！

題目

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

這一題顧名思義就是要我們檢查一串括號是否為合法括號，而合法括號的要件是要左括號等於右括號的數量，並且要兩兩成對，且相同類型的括號要配相同類型的括號（譬如大括號要配大括號）。如果是合法括號就回傳true，否則回傳false。

堆疊 Stack

堆疊是一種儲存資料的方式，其最大的特色就是具有後進先出（LastInFirstOut=>LIFO）的特性，在這一題括號合法的問題上，正好可以利用這樣的特性解，原因是括號的邏輯與之正好相符，一個合法括號，由於是兩兩相對，第一個是對到最後一個，第二個對到倒數第二個，因此永LIFO的原則，正好可以讓第一個與最後一個做比對，形成兩兩比對的規則，以下會跟清楚講解在此題的應用方式。

堆疊解法

此解法會先建立一個堆疊，假如括號為左括號就先加入堆疊，如果是右括號則比對與堆疊最上層的括號是否成對，如果是的話就把最上層的括號丟掉（用pop），最後再檢查堆疊中是否還有括號，如果沒有就表示這是一個合法的括號，如果有則非合法括號。
在python中我們可以透過對list的操作，包括list[-1]、list.append()與list.pop()的方式模擬一個堆疊的資料型態，因為這些操作的時間複雜度都是big O(1)的，因此不會過於浪費時間。而在C++中可以使用stack內建的資料型態進行相對應的函數處理，以下展示兩種不同語言的程式碼。

以下是python的程式碼

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if not stack:
                stack.append(i)
            elif (i == ")" and stack[-1] == "(") or \
                (i == "]" and stack[-1] == "[") or \
                    (i == "}" and stack[-1] == "{"):
                stack.pop()
            else:
                stack.append(i)

        if not stack:
            return True
        else:
            return False

以下是C++的程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  //創建堆疊
        for(char i: s){
            if (st.empty() || i == '(' || i == '[' || i == '{'){
                st.push(i);  //如果是左括號或堆疊為空，就加入堆疊
            }
            else if (i == ')' && st.top() == '(' || i == ']' && st.top() == '[' || 
                    i == '}' && st.top() == '{'){
                st.pop();  //如果是右括號，比對相符就把堆疊最上層丟掉
            }
            else{
                return false; //如果皆非上述情形，表示括號非法，回傳flase
            }   
        }
        return st.empty();  //最後如果堆疊為空就回傳true
    }
};

參考資料